#ifndef SORT_H
#define SORT_H
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
//12345...89ascending ^
//98765...21descending
using namespace std;
class sort_base
{
public:
    sort_base(){printCount=0;}
    virtual ~sort_base(){}
    void inputData(vector<int> _data,int _num){data=_data;num=_num;}
    virtual void sortData()=0;
protected:
    vector<int> data;
    int num;
    void swap(int&a,int&b)
    {
        int c=a;
        a=b;
        b=c;
        printCurrentState();
    }
    void swap2(int&a,int&b)
    {
        b=a+b;
        a=b-a;
        b=a-b;
    }
    void printCurrentState()
    {
        printCount++;
        std::cout<<printCount<<"\t";
        for (int i = 0; i < num; ++i)
        {
            std::cout<<" "<<data[i]<<" ";
        }
        std::cout<<std::endl;
    }
    int printCount;
};

class sort_Bubble : public sort_base//冒泡<交换<比较
{
public:
    sort_Bubble(){}
    ~sort_Bubble(){}
    sort_Bubble(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        bubbleSort();
    }
private:
    void bubbleSort()
    {
        for (int i=0;i < num;i++)
        {
            for (int k=i;k < num;k++)
            {
                if( data[i] > data[k])
                {
                    swap(data[i], data[k]);
                }
            }
        }
    }
};

class sort_QuickSort : public sort_base//快排<交换<比较
{
public:
    sort_QuickSort(){}
    ~sort_QuickSort(){}
    sort_QuickSort(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        quickSort(0, num-1);
    }
private:
    int partition(int left,int right)
    {
        int i=left;//不从left+1开始是为了left可以作为index返回，避免漏掉left最小的情况
        int k=right;
        while(i!=k)
        {
            while(data[k]>data[left] && i<k)
            {
                k--;
            }
            while(data[i]<=data[left] && i<k)//因此从left开始，所以要包含等于的情况，避免i指针无法右移
            {
                i++;
            }
            if(k>i)//可以通过检查减少一次i==k交换，也可以无脑交换以便减少检查，但是不建议
            {swap(data[i], data[k]);}
        }
        if(i>left)//可以通过检查减少一次i==left交换，也可以无脑交换以便减少检查，但是不建议
        {swap(data[left], data[i]);}//current:i==k
        return i;//current:i==k
    }
    void quickSort(int left,int right)
    {
        if(left<right)
        {
            int index = partition(left,right);
            quickSort(left,index-1);
            quickSort(index+1,right);
        }
    }
};

class sort_QuickSort2 : public sort_base//快排<交换<比较
{
public:
    sort_QuickSort2(){}
    ~sort_QuickSort2(){}
    sort_QuickSort2(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        quickSort(0, num-1);
    }
private:
    int partition2(int left,int right)
    {
                    // 设定基准值（pivot=left）
         int   index = left + 1;
        for(int i = index; i <= right; i++)
        {
            if(data[i] < data[left])
            {
                if(index<i)//可以通过检查减少一次index==i交换，也可以无脑交换以便减少检查，但是不建议
                {swap(data[i] , data[index]);}
                index++;
            }
        }
        index--;
        if(index>left)//可以通过检查减少一次index==left交换，也可以无脑交换以便减少检查，但是不建议
        {swap(data[left] , data[index]);}
        return index;
    }
    void quickSort(int left,int right)
    {
        if(left<right)
        {
            int index = partition2(left,right);
            quickSort(left,index-1);
            quickSort(index+1,right);
        }
    }
};

class sort_Insertion1: public sort_base//插入<插入（赋值）<比较
{
public:
    sort_Insertion1(){}
    ~sort_Insertion1(){}
    sort_Insertion1(vector<int> _data,int _num){ inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        insertionSort();
    }
private:
    void insertionSort()
    {
        for (int i=1;i< num;i++)
        {
            int index=i-1;//留存，避免随着index指针移动而移动
              while(index>=0 && ( data[index+1] < data[index]))//如果和前一个相比，已经是current比较xiao那么循环也就可以结束了，因为插入排序总是在在每轮完成后，当前位置以前的所有数据是有序的
            {
                swap(data[index+1], data[index]);//交换
                index--;
            }
        }

    }
};

class sort_Insertion2: public sort_base//插入<插入<比较
{
public:
    sort_Insertion2(){}
    ~sort_Insertion2(){}
    sort_Insertion2(vector<int> _data,int _num){ inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        insertionSort();
    }
private:
    void insertionSort()
    {
        for (int i=1;i< num;i++)
        {
            int index=i-1;//留存，避免随着index指针移动而移动
            int current =data[i];//留存用来"比较和"赋值
            while(index>=0 && ( current < data[index]))//如果和前一个相比，已经是current比较大那么循环也就可以结束了，因为插入排序总是在在每轮完成后，当前位置以前的所有数据是有序的
            {
                data[index+1]= data[index];//赋值
                index--;
                printCurrentState();
            }
            data[index+1]=current;//留存用来赋值,index每次赋值完都需要index--进行下一次查询 && index=i-1;因此还需要+1补回来,index must be less than i,since index = i-1 && index--(conditionally)
            printCurrentState();
        }
    }
};

class sort_Shell1: public sort_base//希尔<插入<比较
{
public:
    sort_Shell1(){}
    ~sort_Shell1(){}
    sort_Shell1(vector<int> _data,int _num){ inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        shellSort();
    }
private:
    void shellSort()
    {
        for (int gap=num/2;gap>0;gap=gap/2)//group it!
        {
            //familiar with instertion ,except -1 & -gap
            for(int i=gap;i<num;i++)//分组执行->实际操作是多个分组交替执行
            {
                int index = i;
                while (index-gap>=0 && (data[index]<data[index-gap]))//index-gap must > 0,else it index cross the boundaty of data
                {
                    swap(data[index],data[index-gap]);
                    index=index-gap;//familiar with instertion ,except -1 & -gap
                }
            }
        }
    }
};

class sort_Shell2: public sort_base//希尔<插入<比较
{
public:
    sort_Shell2(){}
    ~sort_Shell2(){}
    sort_Shell2(vector<int> _data,int _num){ inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        shellSort();
    }
private:
    void shellSort()
    {
        for (int gap=num/2;gap>0;gap=gap/2)//group it!
        {
            for(int i=gap;i<num;i++)//分组执行->实际操作是多个分组交替执行
            {
                int index = i;
                int current = data[index];
                while (index-gap>=0 && (current<data[index-gap]))//index-gap must > 0,else it index cross the boundaty of data
                {
                    data[index]=data[index-gap];
                    index=index-gap;//familiar with instertion ,except -1 & -gap
                    printCurrentState();
                }
                if(index<i)
                {
                    data[index]=current;//留存用来赋值,index每次赋值完都需要index-=gap进行下一次查询 && index=i;因此不需要+gap补回来
                    printCurrentState();
                }
            }
        }
    }
};
class sort_Selection : public sort_base//选择<选择<比较
{
public:
    sort_Selection(){}
    ~sort_Selection(){}
    sort_Selection(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        selectionSort();
    }
private:
    void selectionSort()
    {
        for (int i=0;i < num;i++)
        {
            int index=i;
            for (int k=i;k < num;k++)
            {
                if( data[index] > data[k])
                {
                    index=k;
                }
            }
            swap(data[i], data[index]);
        }
    }
};
class sort_Heap : public sort_base//堆  <选择<比较
{
public:
    sort_Heap(){}
    ~sort_Heap(){}
    sort_Heap(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        heapSort();
    }
private:
    void heapSort()
    {
        for (int i=0;i<num-1;i++)
        {
            heapify(num-i);//从首到尾指针进行大堆排序，排序后首指针的值一定最大
            swap(data[0],data[num-1-i]);//交换首尾指针内容，尾指针的值一定最大，然后尾指针每次循环前移一次
        }
    }
    void heapify(int num)
    {
        /***heapify_Num_Node**/
        for (int i=num/2;i>=0;i--) //since 2^0+2^1+2^2.....+2^(n-1)<2^n ,so last row is the half witch no need heapify
        {
            /******heapify_1_Node******/
            //int father = (i-1)/2//with child index is i,find father index
            int left=2*i+1;//with father index is i,find child left index
            int right=2*i+2;//with father index is i,find child right index

            if(left<num && data[left]>data[i])
            {
                swap(data[left],data[i]);
            }
            if(right<num && data[right]>data[i])
            {
                swap(data[right],data[i]);
            }
            /******heapify_1_Node******/
        }
    }

};

class sort_Merge : public sort_base//归并<归并<比较
{
public:
    sort_Merge(){}
    ~sort_Merge(){}
    sort_Merge(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        int *tmp =new int[num];
        mergeSort(0,num-1,tmp);
    }
private:
    void mergeSort(int left,int right,int *tmp)
    {
        if(left<right)
        {
            //devide
            int middle=(right+left)/2;
            if(middle>left)
            {
                mergeSort(left,middle,tmp);
                mergeSort(middle+1,right,tmp);
            }

            //merge
            int i=left;
            int j=middle+1;
            int m=left;
            while(i<=middle && j<=right)
            {
                if(data[i]<data[j])
                {
                    tmp[m++]=data[i++];
                }
                else
                {
                    tmp[m++]=data[j++];
                }
            }

            while(i<=middle)
            {tmp[m++]=data[i++];}

            while(j<=right)
            {tmp[m++]=data[j++];}

            for(int m=left;m<=right;m++)
            {data[m]=tmp[m];}

            printCurrentState();
        }
    }
};

class sort_Counting : public sort_base//归并<归并<比较
{
public:
    sort_Counting(){}
    ~sort_Counting(){}
    sort_Counting(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        if(num<=1)
            return;
        countingSort();
    }
private:
    void countingSort()
    {
        int minE=10000;
        int maxE=-10000;
        for (int i=0;i<num;i++)
        {
            if (minE>data[i])
            {
                minE=data[i];
            }
            if(maxE<data[i])
            {
                maxE=data[i];
            }
        }
        int len=maxE-minE;
        int *tmp=new int[len+1];
        for (int i=0;i<num;i++)
        {
            tmp[data[i]-minE]+=1;
        }
        int count=0;
        for (int i=0;i<len+1;i++)
        {
            while(tmp[i]!=0)
            {
                data[count++]= i+minE;
                tmp[i]-=1;
                printCurrentState();
            }
        }
    }
};

class sort_Bucket : public sort_base//归并<归并<比较
{
public:
    sort_Bucket(){}
    ~sort_Bucket(){}
    sort_Bucket(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        bucketSort();
    }
private:
    void bucketSort()
    {
        int minE=10000;
        int maxE=-10000;
        for (int i=0;i<num;i++)
        {
            if (minE>data[i])
            {
                minE=data[i];
            }
            if(maxE<data[i])
            {
                maxE=data[i];
            }
        }

        int bucketSize=5;
        int len=(maxE-minE)/bucketSize+1;

        int tmp[bucketSize][len+1];
        memset(tmp,0,sizeof(tmp));
        for (int i=0;i<num;i++)
        {
            int bckt=((data[i]-minE)/len);
            tmp[bckt][(data[i]-minE)%len]+=1;
        }
        int count=0;
        for (int i=0;i<bucketSize;i++)
        {
            for (int j=0;j<len+1;j++)
            {
                while(tmp[i][j]!=0)
                {
                    data[count++]= i*len+j+minE;
                    tmp[i][j]-=1;
                    printCurrentState();
                }
            }
        }

    }
};

class sort_Radix : public sort_base//归并<归并<比较
{
public:
    sort_Radix(){}
    ~sort_Radix(){}
    sort_Radix(vector<int> _data,int _num){inputData(_data,_num);sortData();}
    void sortData()
    {
        printCurrentState();
        countingSort();
    }
private:
    void countingSort()
    {
        int maxE=-10000;
        for (int i=0;i<num;i++)
        {
            if(maxE<data[i])
            {
                maxE=data[i];
            }
        }

        int radix=1;
        while(maxE/radix>1)
        {
            int tmp[10][num+1];//index 0 is the place to counting num of each set, so:[10][num+1]
            memset(tmp,0,sizeof (tmp));
            for (int i=0;i<num;i++)
            {
                int index=data[i]%(radix*10)/radix;
                tmp[index][0]+=1;
                tmp[index][tmp[index][0]]=data[i];//index 0 is the place to counting num of each set, and [index][1] is the beginning of number container index;+1 have already done.

            }
            int index=0;
            for (int i=0;i<10;i++)
            {
                for(int j=0; j<tmp[i][0]; j++)
                {
                    data[index++]=tmp[i][j+1];//[index][1] is the beginning of number container index;
                    printCurrentState();
                }
            }
            radix=radix*10;//must be multi for ascending sort
        }
    }
};
#endif // SORT_H
